//题目:
// 给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
// 商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
// 请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
#include<iostream>
#include<stack>
#include<vector>

using namespace std;
//代码:
class Solution 
{
public:
    vector<int> finalPrices(vector<int>& prices) 
    {
        vector<int> ret;
        vector<pair<int,int>> v;
        //1.将prices中的元素倒着插入st中，要求：所插入元素必须比其前一个元素值小
        for(int i=prices.size()-1;i>=0;i--)
            if(i-1>=0 && prices[i]<=prices[i-1])
                v.push_back(make_pair(i,prices[i]));
        //2.正序遍历prices，同时与st中的元素作比较，注意出栈条件
        for(int j=v.size()-1;j>=0;j--)
            cout<<v[j].second<<endl;
        for(int i=0;i<prices.size();i++)
        {
            //pair<int,int> pir=v.size()>=0?v[v.size()-1]:make_pair(-1,-1);
            if(v.size()>0 && v[v.size()-1].first==i) v.erase(v.begin()+v.size()-1);
            //找出prices[i]后面的符合题目要求的最小下标
            if(v.size()>=0)
            {
                int diff=0;
                for(int j=v.size()-1;j>=0;j--)
                    if(v[j].second<=prices[i])
                    {
                        diff=v[j].second;
                        break;
                    }
                ret.push_back(prices[i]-diff);
            }
            else 
                ret.push_back(prices[i]);   
        }
        return ret;
    }
};